package bfsalgorithm;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

/**
 * 433、最小基因变化
 */
public class Exercise6 {
    public int minMutation(String startGene, String endGene, String[] bank) {
        Set<String> visit = new HashSet<>(); // 用来记录变化后的 字符串 是否判断过
        Set<String> hash = new HashSet<>(); // 用来记录基因库bank的字符串的值
        for(String s : bank) {
            hash.add(s);
        }
        char[] change = {'A','C','G','T'}; // 用于改变 字符串 用的
        if(startGene.equals(endGene)) {
            return 0;
        }
        if(!hash.contains(endGene)) {
            return -1;
        }

        Queue<String> queue = new LinkedList<>();
        queue.add(startGene);
        visit.add(startGene);
        int step = 0;

        while(!queue.isEmpty()) {
            step++;
            int size = queue.size();
            while(size-- != 0) {
                String t = queue.poll();
                for(int i = 0;i < 8;i++) {
                    char[] tmp = t.toCharArray();
                    for(int k = 0;k < 4;k++) {
                        // 每一个都存在四个变换
                        tmp[i] = change[k];
                        // 变换之后，再改成字符串
                        String next = new String(tmp);
                        // 要判断是否是基因库的值
                        if(hash.contains(next) && !visit.contains(next)) {
                            if(next.equals(endGene)) {
                                return step;
                            }
                            queue.add(next);
                            visit.add(next);
                        }
                    }
                }
            }
        }
        return -1;
    }
}
